Signal processing is an important function of many electronic systems. In particular, in many electronic systems, data is transmitted in signal form. Further, some electronic systems analyze and monitor the operation of mechanical or chemical systems by observing the characteristics of signals, such as vibration signals and other types of signals, that are output from these systems. In light of this, methods have been developed to characterize signals such that information or data in the signal is available for data processing.
As one example, in many electronic systems, time domain signals are typically transformed to the frequency domain prior to signal processing. A typical method for converting signals to the frequency domain is performed using Fourier Transforms. The Fourier Transform of a signal is based on a plurality of samples of the time domain signal taken over a selected time period, known as the base frequency. Based on these samples of the signal the Fourier Transform provides a plurality of coefficients, where the coefficients respectively represent the amplitude of a frequency that is a multiple of the base frequency. These coefficients of the Fourier Transform, which represent the signal in the frequency domain, are then used by electronic systems in processing the signal.
Although Fourier Transforms are among some of the most widely used functions for processing signals, there are other functions that are either currently used or will be used in the future, as a better understanding of their applicability is recognized. These functions include Bessel functions, Legendre Polynomials, Tschebysheff Polynomials of First and Second Kind, Jacoby Polynomials, Generalized Laguerre Polynomials, Hermite Polynomials, Bernoulli Polynomials, Euler Polynomials, and a variety of Matrices used in Quantum Mechanics, Linear Analysis functions, wavelets and fractals just to name a few.
Although Fourier transforms and the other functions mentioned above are useful in determining characteristics of signals for use in data processing, there can be some drawbacks to their use. Specifically, application of these functions to signals is typically computationally intensive. This is disadvantageous, as it may require the use of specialized processors in order to perform data processing. Further, and even more importantly, the time required to perform the number of computations using these functions may cause an unacceptable delay for many data processing applications. In fact, a goal of many data processing systems is the ability to process data signals in real time, with no delay.
For example, the Fourier Series is defined as an infinite series of coefficients representing a signal. To transform a signal using a Fourier Series would require an infinite number of computations. To remedy this problem, many conventional data processing systems use Discrete Fourier Transforms (DFT), as opposed to the infinite Fourier Series. The DFT is the digital approximation to the Fourier Series and is used to process digitized analog information. Importantly, the DFT replaces the infinite series of the Fourier Series with a finite set of N evenly spaced samples taken over a finite period. The computation of the DFT therefore provides the same number of coefficients as the samples received, instead of an infinite number of samples required by the Fourier Series. As such, use of the DFT provides the most satisfactory current means to process the signal.
Because of the importance of reducing the time required to process signals, however, methods have been developed to further reduce the number of computations required to perform a DFT of a signal. Specifically, the DFT procedure computes each coefficient by a similar process. The process for a general coefficient is; multiply each sample by the sine or cosine of the normalized value of the independent variable times the angular rate and sum over all of the samples. This procedure defines N multiply-add steps for each of N coefficients, which in turn, equates to N2 multiply-add computations per DFT. As many samples of a signal are typically required to perform an adequate approximation of the signal, the DFT of a signal is typically computational and time intensive.
One of the methods developed to reduce the number of computations is the butterfly method, which reduces the number of computations from N2 to N times log (N). The butterfly method is based on the fact that many of the trigonometric values of the DFT are the same due to periodicity of the functions. As such, the butterfly method reduces the matrix associated with the DFT into N/2 two-point transforms (i.e., the transforms representing each coefficient an and bn). The butterfly method further reduces the redundant trigonometric values of the DFT.
Although the butterfly method reduces the number of computations over the more traditional DFT method, it also adds complexity to the Fourier transformation of a signal. Specifically, the butterfly method uses a complex method for addressing the samples of the signal and the matrix containing the functions. This complexity can require the use of specialized processors and increase time for computation of the Fourier Transform. By its nature, the butterfly is a batch process, which does not begin determination of the coefficients until after all of the samples have been received. Consequently, this method causes latency in the determination of the coefficients of the function, where the time between the arrival of the last sample and the availability of the coefficients is defined as the latency of the system.
Another approach to reducing the time required to process signals is described in U.S. patent application Ser. No. 09/560,221, filed Apr. 28, 2000, and entitled: “Apparatus, Methods And Computer Program Products For Determining The Coefficients Of A Function With Decreased Latency” and in PCT Application No. WO 00/67146, entitled: “Computation of Discrete Fourier Transform”, published Nov. 9, 2000, the contents of which are incorporated herein by reference. Both of these patent applications were invented and are owned by Mr. Walter Pelton, who is also a co-inventor and assignee of the present application. Pelton's approach as described more fully in these applications reduces or eliminates the problem of latency for processing coefficients by using an important property of functions like the DFT to reduce the latency. This property is the independence of samples. In a set of samples being transformed in a DFT process, each sample makes a contribution to each coefficient based only on the sine or cosine of the applicable angle. Specifically, each of the coefficients of the DFT is the summation of the application of each sample to the sine and cosine functions associated with each coefficient. As each of the samples are related to each coefficient by addition, each sample is independent of the other samples and can be used to update the coefficients prior to receipt of the other samples.
Using Pelton's approach, a complete set of coefficients can be derived for a plurality of samples. Specifically, as each sample is received, the coefficient contributions for each sample is calculated. Also, the coefficient contributions are summed after they are calculated. After adding the coefficient contributions for the last sample of the plurality of samples, a complete set of coefficients is available for all of the samples. The time required to calculate and add the contribution of the last sample is typically small. Consequently, the latency of the Pelton approach is characteristically small.
In U.S. patent application Ser. No. 09/560,221 and PCT application WO 00/67146, a Sliding Aperture Fourier Transform (SAFT) is described, along with apparatus, methods, and computer program products for performing such transforms. Processing Sliding Aperture Fourier Transforms (SAFT) includes replacing the coefficient contributions of the oldest sample of the previous plurality of samples with the coefficient contributions of the next received sample. Using this new sample, SAFT yields a next set of coefficients that are available for output. As such, instead of generating a set of coefficients for each “batch” of samples, SAFT generates a set of coefficients each time a new sample is received. An important characteristic of the operation of SAFT is that SAFT uses the previously calculated coefficient contributions for samples that have been received. SAFT provides a complete set of coefficients for the batch of samples by subtracting the coefficient contributions for the oldest sample and adding the coefficient contributions for a new sample each time a new sample is received.
It is apparent that the Pelton approach and Sliding Aperture Fourier Transforms as described in WO 00/67146 can be used in numerous applications. A few of the advantages of the Pelton approach and the SAFT are: low or zero latency coefficient processing capabilities, reduced hardware requirements, simpler programming requirements, simpler electronic devices for implementation, to reduce the power consumption for electronically processing coefficients, and more information for the samples of data. However, there may be applications in which it may be desirable for SAFT, as described in U.S. patent application Ser. No. 09/560,221 and PCT Application WO 00/67146, to provide coefficients of greater accuracy.
Specifically, SAFT as described in these applications introduces an error in the calculated coefficients at the start of the process of subtracting the coefficient contribution of the oldest sample and adding the coefficient contribution of the new sample. Error may occur because the continuous processing of the coefficients causes a shift in the angle associated with each sample. For example, in DFT applications, a particular angle is associated with the first sample of a set of N samples, and that angle is used in calculating the coefficient contributions for the first sample. Similarly, a particular angle is associated with the second sample and so on for each of the N samples in the “batch.” SAFT, on the other hand, maintains a batch of samples in which one sample is continually changing. If there are eight samples (i.e., N=8), this means that the oldest sample, sample 1, is removed and the previous sample 2 now becomes sample 1. This occurs for each of the samples so that the new sample becomes sample 8. However, the coefficients that are updated during SAFT were derived from calculations of the coefficient contributions where the samples were matched with the angles from the previous position. In other words, the updated coefficients include the error of calculating the coefficient contributions using angles that apply to the earlier sample.
Specifically, SAFT as described in WO 00/67146 introduces an error in the calculated coefficients at the start of the process of subtracting the coefficient contribution of the oldest sample and adding the coefficient contribution of the new sample. The error occurs because the continuous processing of the coefficients causes a shift in the angle associated with each sample. For example, in DFT applications, a particular angle is associated with the first sample and that angle is used in calculating the coefficient contributions for the first sample. Similarly, a particular angle is associated with the second sample and so on for each sample in the “batch.” SAFT maintains a batch of samples in which one sample is continually changing. If there are eight samples, this means that the oldest sample, sample 1, is removed and the previous sample 2 now becomes sample 1. This occurs for each of the samples so that the new sample becomes sample 8. However, the coefficients that are updated during SAFT were derived from calculations of the coefficient contributions where the samples were matched with the angles from the previous position. In other words, the updated coefficients include the error of calculating the coefficient contributions using angles that apply to the earlier sample.
In an ideal SAFT process, as a new sample is received after the initial 8 samples (i.e., N=8), sample 2 should take the position in the calculations for sample 1 and use the corresponding angle for sample 1 in generating the coefficient contributions and so on for each following sample. However, this problem was not specifically addressed in the SAFT application described in U.S. patent application Ser. No. 09/560,221 and PCT Application WO 00/67146. Instead, the SAFT described in these patent applications uses the previously calculated coefficients as they are for deriving the updated coefficients that include the new sample. In other words, as a new sample is received after the original N samples have been processed, the SAFT as described in these applications merely subtract the contributions of the first sample N=0 and adds the contributions of the new sample. The SAFT as described in these two patent applications does not describe shifting the samples 2-8 previously received such that they take the position in the calculations for the sample below them and use the corresponding angle for the sample position below them to generate an updated set of coefficients. Instead, the contributions to the coefficients by the second sample of the original set of samples, which is now the first sample of the new set, are still based on the angle associated with the second sample and not the angle of the first sample.
Consequently, there is a need for SAFT calculation capabilities that perform rapidly and with high accuracy for processing coefficients. In addition, there is still a general need for improved methods, apparatus, and computer program products for processing coefficients of functions with greater speed and greater efficiency.